package com.vint.leetcode;


import com.vint.common.ListNode;


/*
 * 1. done
 * 2. easy
 * 3. tree, 递归
 * 判断两棵树是否相等
 */
public class Leetcode19 {

	public ListNode removeNthFromEnd(ListNode head, int n) {
		if (null == head) return head;
		if (null == head.next && n == 1) return null;
		ListNode root = new ListNode(0);
		ListNode pre = root;
		ListNode after = root;
		int step = n;
		while(step-- != 0){
			pre = pre.next;
			if (null == pre) {
				return head;
			}
		}
		while (null != pre.next) {
			after = after.next;
			pre = pre.next;
		}
		if (after == root) {
			return head.next;
		}
		after.next = after.next.next;
		return head;
	}
    public static void main(String[] args) {
		Leetcode19 leetcode19 = new Leetcode19();
		ListNode root = new ListNode(1);
	    root.next = new ListNode(2);
	    root.next.next = new ListNode(3);
	    leetcode19.removeNthFromEnd(root,3);
	    ListNode rootd = new ListNode(1);
    }
  }
